|
In computational number theory, the Lucas test is a primality test for a natural number ''n''; it requires that the prime factors of ''n'' − 1 be already known. It is the basis of the Pratt certificate that gives a concise verification that ''n'' is prime. ==Concepts== Let ''n'' be a positive integer. If there exists an integer 1 < ''a'' < ''n'' such that : and for every prime factor ''q'' of ''n'' − 1 : then ''n'' is prime. If no such number ''a'' exists, then ''n'' is either 1 or composite. The reason for the correctness of this claim is as follows: if the first equivalence holds for ''a'', we can deduce that ''a'' and ''n'' are coprime. If ''a'' also survives the second step, then the order of ''a'' in the group (Z/''n''Z) * is equal to ''n''−1, which means that the order of that group is ''n''−1 (because the order of every element of a group divides the order of the group), implying that ''n'' is prime. Conversely, if ''n'' is prime, then there exists a primitive root modulo ''n'', or generator of the group (Z/''n''Z) *. Such a generator has order |(Z/''n''Z) *| = ''n''−1 and both equivalences will hold for any such primitive root. Note that if there exists an ''a'' < ''n'' such that the first equivalence fails, ''a'' is called a Fermat witness for the compositeness of ''n''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Lucas primality test」の詳細全文を読む スポンサード リンク
|